#define _CRT_SECURE_NO_WARNINGS	

typedef char DataType;
typedef struct Stack
{
    DataType* arr;
    int top;
    int capacity;
}Stack;

void Init_Stack(Stack* st)
{
    st->arr = NULL;
    st->top = st->capacity = 0;
}

void Destory_Stack(Stack* st)
{
    if (st->arr)
        free(st->arr);
    st->arr = NULL;
    st->top = st->capacity = 0;
}

bool Empty_Stack(Stack* st)
{
    assert(st);
    return st->top != 0;
}

void Push_Stack(Stack* st, DataType x)
{
    assert(st);
    if (st->top == st->capacity)
    {
        int newcapacity = st->capacity ? 2 * st->capacity : 4;
        DataType* tmp = (DataType*)realloc(st->arr, newcapacity * sizeof(DataType));
        if (!tmp)
        {
            perror("realloc fail!");
            exit(1);
        }
        st->arr = tmp;
        st->capacity = newcapacity;
    }
    st->arr[st->top++] = x;
}

void Pop_Stack(Stack* st)
{
    assert(Empty_Stack(st));
    st->top--;
}

DataType Get_Top_Stack(Stack* st)
{
    assert(Empty_Stack(st));
    return st->arr[st->top - 1];

}

bool isValid(char* s)
{
    Stack st;
    Init_Stack(&st);
    char* pi = s;
    while (*pi != '\0')
    {
        if (*pi == '(' || *pi == '{' || *pi == '[')
        {
            Push_Stack(&st, *pi);
        }
        else
        {
            if (!Empty_Stack(&st))
            {
                Destory_Stack(&st);
                return false;
            }
            char tmp = Get_Top_Stack(&st);
            if ((tmp == '(' && *pi != ')') || (tmp == '[' && *pi != ']') || (tmp == '{' && *pi != '}'))
            {
                Destory_Stack(&st);
                return false;
            }
            Pop_Stack(&st);
        }
        pi++;
    }
    if (Empty_Stack(&st))
    {
        Destory_Stack(&st);
        return false;
    }
    return true;
}